package three;
import java.util.*;

public class A052 {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //拓扑排序

        //
        Queue<Integer> queue = new LinkedList<>();
        int n = numCourses; //0-n-1
        int[] in = new int[n];//用来统计入度，也就是有多少个数字指向他
        Map<Integer,List<Integer>> edges = new HashMap<>();//建立邻接矩阵，也就是Integer一共指向哪些数字
        //1.建邻接矩阵和收集入度
        for(int i=0;i<prerequisites.length;i++) {
            int a = prerequisites[i][0], b = prerequisites[i][1];  //b-->a  //完成a课程需要先学b,所以a被指向
            //1.邻接矩阵
            if(!edges.containsKey(b)) edges.put(b,new ArrayList<>());
            edges.get(b).add(a);
            //2.入度
            in[a]++;
        }

        //2.把入度为0的加入队列
        for(int i=0;i<n;i++) {
            if(in[i]==0) queue.add(i);
        }
        //3.拓扑排序
        while(!queue.isEmpty()) {
            int t = queue.poll();
            //去掉t指向的边
            for(int x:edges.getOrDefault(t,new ArrayList<>())) {
                in[x]--;
                if(in[x]==0) queue.add(x);
            }
        }

        for(int x:in) {
            if(x!=0) return false;
        }
        return true;
    }
}
